package com.xiaoma.suanfa.leetcode;

import java.util.ArrayList;
import java.util.List;

public class PhoneNumber {

    public static void main(String[] args) {
        List<String> str= letterCombinations("56");
        System.out.println(str);
    }

    public static List<String> letterCombinations(String digits) {

        List<String> list = new ArrayList<>();

        if (digits.isEmpty()) {
            return list;
        }

        String[] strings = new String[]{"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

        letterCombinationsDFS(digits, strings, 0, new StringBuilder(), list);

        return list;
    }

    public static void letterCombinationsDFS(String digits, String[] strings, int level, StringBuilder out, List<String> list) {

        //如果已经到达最后一层，则把字符串添加进列表
        if (level == digits.length()) {
            list.add(out.toString());
        } else {
            //获取对应数字的字符串
            String str = strings[digits.charAt(level) - '2'];

            for (int i = 0; i < str.length(); i++) {
                out.append(str.charAt(i));
                //添加完这一层的一个字符之后，继续添加下一层的字符
                letterCombinationsDFS(digits, strings, level + 1, out, list);
                //注意要回退字符串
                out.deleteCharAt(out.length() - 1);
            }
        }

    }
}
